package leetcode.editor.cn;

import java.util.*;

/**
 * Copyright (C) 2023 思创数码科技股份有限公司
 * <p/>
 * 版权所有
 * <p/>
 * 类名　　  : P2332
 * 功能概要  :
 *
 * @author yangwk
 * @date 2024/9/18 9:16
 */
public class P2332 {
    public static void main(String[] args) {
//        int[] buses = new int[]{3};
        int[] buses = new int[]{3};
//        int[] passengers = new int[]{2, 3};
        int[] passengers = new int[]{2,4};
        int capacity = 2;
        System.out.println(latestTimeCatchTheBus(buses, passengers, capacity));

    }

    public static int latestTimeCatchTheBus(int[] buses, int[] passengers, int capacity) {
        Arrays.sort(buses);
        List<List<Integer>> carry = new ArrayList<>();
        TreeSet<Integer> treeSet = new TreeSet<>();
        for (int passenger : passengers) {
            treeSet.add(passenger);
        }
        List<Integer> path = new ArrayList<>();
        for (int i = 0; i < buses.length; i++) {
            int bus = buses[i];
            if (i > carry.size() - 1) {
                carry.add(new ArrayList<>());
            }
            NavigableSet<Integer> minPassengerSet = treeSet.headSet(bus, true);
            for (int j = 0; j < capacity && !minPassengerSet.isEmpty(); j++) {
                Integer passenger = minPassengerSet.pollFirst();
                carry.get(i).add(passenger);
                path.add(passenger);
            }
        }
        int index = 0;
        if (path.isEmpty()) {
            index = buses[buses.length - 1];
        } else {
            List<Integer> lastCarry = carry.get(buses.length - 1);
            if (lastCarry.size() < capacity && (lastCarry.isEmpty() || lastCarry.get(lastCarry.size() - 1) < buses[buses.length - 1])) {
                index = buses[buses.length - 1];
            } else {
                for (int i = path.size() - 1; i >= 0; i--) {
                    Integer integer = path.get(i);
                    if (i == 0) {
                        index = integer - 1;
                        break;
                    } else {
                        Integer preInteger = path.get(i - 1);
                        if (preInteger != integer - 1) {
                            index = integer - 1;
                            break;
                        }
                    }

                }
            }
        }
        return index;
    }
}
